package com.cdream.basic.algorithm.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author cdream
 * @date 2022/3/16
 */
public class LFU {
    public static void main(String[] args) {
        AllOne allOne = new AllOne();
        allOne.inc("a");
        allOne.inc("b");
        allOne.inc("b");
        allOne.inc("c");
        allOne.inc("c");
        allOne.inc("c");
        allOne.dec("b");
        allOne.dec("b");
        System.out.println(allOne.getMinKey());
        System.out.println(allOne);
    }
}
class AllOne {
    Map<String,Node> map = new HashMap<>();
    Node root = new Node();
    public AllOne() {
        root.next = root;
        root.prev = root;
    }

    public void inc(String key) {
        if(map.containsKey(key)){
            Node cur = map.get(key);
            Node curNext = cur.next;
            if(curNext == root || curNext.count > cur.count+1){
                map.put(key,cur.insert(new Node(key,cur.count+1)));
            }else{
                curNext.keys.add(key);
                map.put(key,curNext);
            }
            cur.keys.remove(key);
            if(cur.keys.isEmpty()){
                cur.remove();
            }
        }else{
            Node rNext = root.next;
            if(root.next==root || rNext.count>1){
                map.put(key,root.insert(new Node(key,1)));
            }else {
                rNext.keys.add(key);
                map.put(key,rNext);
            }
        }
    }

    public void dec(String key) {
        Node cur = map.get(key);
        if(cur.count==1){
            map.remove(key);
        }else{
            Node curPrev = cur.prev;
            if(curPrev==root || curPrev.count+1<cur.count){
                map.put(key,curPrev.insert(new Node(key,cur.count-1)));
            }else{
                curPrev.keys.add(key);
                map.put(key,curPrev);
            }
        }
        cur.keys.remove(key);
        if (cur.keys.isEmpty()) {
            cur.remove();
        }

    }

    public String getMaxKey() {
        return root.prev==root?"": root.prev.keys.iterator().next() ;
    }

    public String getMinKey() {
        return root.next==root?"": root.next.keys.iterator().next() ;
    }
}
class Node{
    Node prev;
    Node next;
    Set<String> keys;
    int count;
    public Node(){
        this("",0);
    }
    public Node(String key,int count){
        keys = new HashSet<>();
        keys.add(key);
        this.count = count;
    }
    public void remove(){
        this.prev.next = this.next;
        this.next.prev = this.prev;
    }
    public Node insert(Node node){
        Node nNode = this.next;
        this.next = node;
        node.prev = this;
        node.next = nNode;
        nNode.prev = node;
        return node;
    }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */
